// Time:  O(n * k), n is the number of coins, k is the amount of money
// Space: O(k)

// DP solution. (164ms)

// TODO
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for(const auto& coin : coins) {
            for(int i = coin; i <= amount; ++i) {
                if (dp[i - coin] != INT_MAX) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        if (dp[amount] == INT_MAX) {
            return -1;
        }
        return dp[amount];
    }
};

int main() {
    Solution solution;

    // Test case 1
    std::vector<int> coins1 = {1, 2, 5};
    int amount1 = 11;
    int result1 = solution.coinChange(coins1, amount1);
    assert(result1 == 3); // 11 = 5 + 5 + 1

    // Test case 2
    std::vector<int> coins2 = {2};
    int amount2 = 3;
    int result2 = solution.coinChange(coins2, amount2);
    assert(result2 == -1); // Not possible to make 3 with only 2

    // Test case 3
    std::vector<int> coins3 = {1};
    int amount3 = 0;
    int result3 = solution.coinChange(coins3, amount3);
    assert(result3 == 0); // 0 coins needed to make amount 0

    // Test case 4
    std::vector<int> coins4 = {1, 2, 5};
    int amount4 = 100;
    int result4 = solution.coinChange(coins4, amount4);
    assert(result4 == 20); // 100 = 20 * 5

    // Test case 5
    std::vector<int> coins5 = {1, 2, 5, 10};
    int amount5 = 27;
    int result5 = solution.coinChange(coins5, amount5);
    assert(result5 == 4); // 27 = 10 + 10 + 5 + 2

    std::cout << "All test cases passed!" << std::endl;
}